<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>1、排序的基本概念 | Lionkliu</title>
    <meta name="description" content="Lionkliuの知识库">
    <link rel="stylesheet" href="/vitepress-doc/assets/style.267868d6.css">
    <link rel="modulepreload" href="/vitepress-doc/assets/app.397cc5b7.js">
    <link rel="modulepreload" href="/vitepress-doc/assets/kaoyan_ds_sort.md.73d4d399.lean.js">
    
    <link rel="icon" href="/lyj.png">
  <script>(()=>{const e=localStorage.getItem("vitepress-theme-appearance"),a=window.matchMedia("(prefers-color-scheme: dark)").matches;(!e||e==="auto"?a:e==="dark")&&document.documentElement.classList.add("dark")})();</script>
  </head>
  <body>
    <div id="app"><div class="Layout" data-v-6b5fd0a9><!--[--><!--]--><!--[--><span tabindex="-1" data-v-45f6ae50></span><a href="#VPContent" class="VPSkipLink visually-hidden" data-v-45f6ae50> Skip to content </a><!--]--><!----><header class="VPNav" data-v-6b5fd0a9 data-v-0e356168><div class="VPNavBar has-sidebar" data-v-0e356168 data-v-8856f192><div class="container" data-v-8856f192><div class="VPNavBarTitle has-sidebar" data-v-8856f192 data-v-6a6f7ff6><a class="title" href="/vitepress-doc/" data-v-6a6f7ff6><!--[--><img class="VPImage logo" src="/vitepress-doc/lyj.png" data-v-73ae1788><!--]--><!--[-->Lionkliuの知识库<!--]--></a></div><div class="content" data-v-8856f192><!----><nav aria-labelledby="main-nav-aria-label" class="VPNavBarMenu menu" data-v-8856f192 data-v-a30758ee><span id="main-nav-aria-label" class="visually-hidden" data-v-a30758ee>Main Navigation</span><!--[--><!--[--><a class="VPLink link VPNavBarMenuLink" href="/vitepress-doc/wiki/" data-v-a30758ee data-v-8fba5fa8 data-v-5704c677><!--[-->🍟 知识库<!--]--><!----></a><!--]--><!--[--><a class="VPLink link VPNavBarMenuLink active" href="/vitepress-doc/kaoyan/" data-v-a30758ee data-v-8fba5fa8 data-v-5704c677><!--[-->🍿 考研<!--]--><!----></a><!--]--><!--[--><a class="VPLink link VPNavBarMenuLink" href="/vitepress-doc/menu3/" data-v-a30758ee data-v-8fba5fa8 data-v-5704c677><!--[-->其他<!--]--><!----></a><!--]--><!--]--></nav><!----><div class="VPNavBarAppearance appearance" data-v-8856f192 data-v-311055f2><button class="VPSwitch VPSwitchAppearance" type="button" role="switch" aria-label="toggle dark mode" data-v-311055f2 data-v-781f9d1b data-v-1dda4c9c><span class="check" data-v-1dda4c9c><span class="icon" data-v-1dda4c9c><!--[--><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" viewbox="0 0 24 24" class="sun" data-v-781f9d1b><path d="M12,18c-3.3,0-6-2.7-6-6s2.7-6,6-6s6,2.7,6,6S15.3,18,12,18zM12,8c-2.2,0-4,1.8-4,4c0,2.2,1.8,4,4,4c2.2,0,4-1.8,4-4C16,9.8,14.2,8,12,8z"></path><path d="M12,4c-0.6,0-1-0.4-1-1V1c0-0.6,0.4-1,1-1s1,0.4,1,1v2C13,3.6,12.6,4,12,4z"></path><path d="M12,24c-0.6,0-1-0.4-1-1v-2c0-0.6,0.4-1,1-1s1,0.4,1,1v2C13,23.6,12.6,24,12,24z"></path><path d="M5.6,6.6c-0.3,0-0.5-0.1-0.7-0.3L3.5,4.9c-0.4-0.4-0.4-1,0-1.4s1-0.4,1.4,0l1.4,1.4c0.4,0.4,0.4,1,0,1.4C6.2,6.5,5.9,6.6,5.6,6.6z"></path><path d="M19.8,20.8c-0.3,0-0.5-0.1-0.7-0.3l-1.4-1.4c-0.4-0.4-0.4-1,0-1.4s1-0.4,1.4,0l1.4,1.4c0.4,0.4,0.4,1,0,1.4C20.3,20.7,20,20.8,19.8,20.8z"></path><path d="M3,13H1c-0.6,0-1-0.4-1-1s0.4-1,1-1h2c0.6,0,1,0.4,1,1S3.6,13,3,13z"></path><path d="M23,13h-2c-0.6,0-1-0.4-1-1s0.4-1,1-1h2c0.6,0,1,0.4,1,1S23.6,13,23,13z"></path><path d="M4.2,20.8c-0.3,0-0.5-0.1-0.7-0.3c-0.4-0.4-0.4-1,0-1.4l1.4-1.4c0.4-0.4,1-0.4,1.4,0s0.4,1,0,1.4l-1.4,1.4C4.7,20.7,4.5,20.8,4.2,20.8z"></path><path d="M18.4,6.6c-0.3,0-0.5-0.1-0.7-0.3c-0.4-0.4-0.4-1,0-1.4l1.4-1.4c0.4-0.4,1-0.4,1.4,0s0.4,1,0,1.4l-1.4,1.4C18.9,6.5,18.6,6.6,18.4,6.6z"></path></svg><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" viewbox="0 0 24 24" class="moon" data-v-781f9d1b><path d="M12.1,22c-0.3,0-0.6,0-0.9,0c-5.5-0.5-9.5-5.4-9-10.9c0.4-4.8,4.2-8.6,9-9c0.4,0,0.8,0.2,1,0.5c0.2,0.3,0.2,0.8-0.1,1.1c-2,2.7-1.4,6.4,1.3,8.4c2.1,1.6,5,1.6,7.1,0c0.3-0.2,0.7-0.3,1.1-0.1c0.3,0.2,0.5,0.6,0.5,1c-0.2,2.7-1.5,5.1-3.6,6.8C16.6,21.2,14.4,22,12.1,22zM9.3,4.4c-2.9,1-5,3.6-5.2,6.8c-0.4,4.4,2.8,8.3,7.2,8.7c2.1,0.2,4.2-0.4,5.8-1.8c1.1-0.9,1.9-2.1,2.4-3.4c-2.5,0.9-5.3,0.5-7.5-1.1C9.2,11.4,8.1,7.7,9.3,4.4z"></path></svg><!--]--></span></span></button></div><div class="VPSocialLinks VPNavBarSocialLinks social-links" data-v-8856f192 data-v-0ae890f7 data-v-4dcbaf3a><!--[--><a class="VPSocialLink" href="https://github.com/vuejs/vitepress" title="github" target="_blank" rel="noopener noreferrer" data-v-4dcbaf3a data-v-48c45ef6><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" viewbox="0 0 24 24" class="icon" data-v-48c45ef6><path d="M12 .297c-6.63 0-12 5.373-12 12 0 5.303 3.438 9.8 8.205 11.385.6.113.82-.258.82-.577 0-.285-.01-1.04-.015-2.04-3.338.724-4.042-1.61-4.042-1.61C4.422 18.07 3.633 17.7 3.633 17.7c-1.087-.744.084-.729.084-.729 1.205.084 1.838 1.236 1.838 1.236 1.07 1.835 2.809 1.305 3.495.998.108-.776.417-1.305.76-1.605-2.665-.3-5.466-1.332-5.466-5.93 0-1.31.465-2.38 1.235-3.22-.135-.303-.54-1.523.105-3.176 0 0 1.005-.322 3.3 1.23.96-.267 1.98-.399 3-.405 1.02.006 2.04.138 3 .405 2.28-1.552 3.285-1.23 3.285-1.23.645 1.653.24 2.873.12 3.176.765.84 1.23 1.91 1.23 3.22 0 4.61-2.805 5.625-5.475 5.92.42.36.81 1.096.81 2.22 0 1.606-.015 2.896-.015 3.286 0 .315.21.69.825.57C20.565 22.092 24 17.592 24 12.297c0-6.627-5.373-12-12-12"></path></svg><span class="visually-hidden" data-v-48c45ef6>github</span></a><!--]--></div><div class="VPFlyout VPNavBarExtra extra" data-v-8856f192 data-v-0562f5c0 data-v-8dccea88><button type="button" class="button" aria-haspopup="true" aria-expanded="false" aria-label="extra navigation" data-v-8dccea88><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" viewbox="0 0 24 24" class="icon" data-v-8dccea88><circle cx="12" cy="12" r="2"></circle><circle cx="19" cy="12" r="2"></circle><circle cx="5" cy="12" r="2"></circle></svg></button><div class="menu" data-v-8dccea88><div class="VPMenu" data-v-8dccea88 data-v-e73581a2><!----><!--[--><!--[--><!----><div class="group" data-v-0562f5c0><div class="item appearance" data-v-0562f5c0><p class="label" data-v-0562f5c0>Appearance</p><div class="appearance-action" data-v-0562f5c0><button class="VPSwitch VPSwitchAppearance" type="button" role="switch" aria-label="toggle dark mode" data-v-0562f5c0 data-v-781f9d1b data-v-1dda4c9c><span class="check" data-v-1dda4c9c><span class="icon" data-v-1dda4c9c><!--[--><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" viewbox="0 0 24 24" class="sun" data-v-781f9d1b><path d="M12,18c-3.3,0-6-2.7-6-6s2.7-6,6-6s6,2.7,6,6S15.3,18,12,18zM12,8c-2.2,0-4,1.8-4,4c0,2.2,1.8,4,4,4c2.2,0,4-1.8,4-4C16,9.8,14.2,8,12,8z"></path><path d="M12,4c-0.6,0-1-0.4-1-1V1c0-0.6,0.4-1,1-1s1,0.4,1,1v2C13,3.6,12.6,4,12,4z"></path><path d="M12,24c-0.6,0-1-0.4-1-1v-2c0-0.6,0.4-1,1-1s1,0.4,1,1v2C13,23.6,12.6,24,12,24z"></path><path d="M5.6,6.6c-0.3,0-0.5-0.1-0.7-0.3L3.5,4.9c-0.4-0.4-0.4-1,0-1.4s1-0.4,1.4,0l1.4,1.4c0.4,0.4,0.4,1,0,1.4C6.2,6.5,5.9,6.6,5.6,6.6z"></path><path d="M19.8,20.8c-0.3,0-0.5-0.1-0.7-0.3l-1.4-1.4c-0.4-0.4-0.4-1,0-1.4s1-0.4,1.4,0l1.4,1.4c0.4,0.4,0.4,1,0,1.4C20.3,20.7,20,20.8,19.8,20.8z"></path><path d="M3,13H1c-0.6,0-1-0.4-1-1s0.4-1,1-1h2c0.6,0,1,0.4,1,1S3.6,13,3,13z"></path><path d="M23,13h-2c-0.6,0-1-0.4-1-1s0.4-1,1-1h2c0.6,0,1,0.4,1,1S23.6,13,23,13z"></path><path d="M4.2,20.8c-0.3,0-0.5-0.1-0.7-0.3c-0.4-0.4-0.4-1,0-1.4l1.4-1.4c0.4-0.4,1-0.4,1.4,0s0.4,1,0,1.4l-1.4,1.4C4.7,20.7,4.5,20.8,4.2,20.8z"></path><path d="M18.4,6.6c-0.3,0-0.5-0.1-0.7-0.3c-0.4-0.4-0.4-1,0-1.4l1.4-1.4c0.4-0.4,1-0.4,1.4,0s0.4,1,0,1.4l-1.4,1.4C18.9,6.5,18.6,6.6,18.4,6.6z"></path></svg><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" viewbox="0 0 24 24" class="moon" data-v-781f9d1b><path d="M12.1,22c-0.3,0-0.6,0-0.9,0c-5.5-0.5-9.5-5.4-9-10.9c0.4-4.8,4.2-8.6,9-9c0.4,0,0.8,0.2,1,0.5c0.2,0.3,0.2,0.8-0.1,1.1c-2,2.7-1.4,6.4,1.3,8.4c2.1,1.6,5,1.6,7.1,0c0.3-0.2,0.7-0.3,1.1-0.1c0.3,0.2,0.5,0.6,0.5,1c-0.2,2.7-1.5,5.1-3.6,6.8C16.6,21.2,14.4,22,12.1,22zM9.3,4.4c-2.9,1-5,3.6-5.2,6.8c-0.4,4.4,2.8,8.3,7.2,8.7c2.1,0.2,4.2-0.4,5.8-1.8c1.1-0.9,1.9-2.1,2.4-3.4c-2.5,0.9-5.3,0.5-7.5-1.1C9.2,11.4,8.1,7.7,9.3,4.4z"></path></svg><!--]--></span></span></button></div></div></div><div class="group" data-v-0562f5c0><div class="item social-links" data-v-0562f5c0><div class="VPSocialLinks social-links-list" data-v-0562f5c0 data-v-4dcbaf3a><!--[--><a class="VPSocialLink" href="https://github.com/vuejs/vitepress" title="github" target="_blank" rel="noopener noreferrer" data-v-4dcbaf3a data-v-48c45ef6><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" viewbox="0 0 24 24" class="icon" data-v-48c45ef6><path d="M12 .297c-6.63 0-12 5.373-12 12 0 5.303 3.438 9.8 8.205 11.385.6.113.82-.258.82-.577 0-.285-.01-1.04-.015-2.04-3.338.724-4.042-1.61-4.042-1.61C4.422 18.07 3.633 17.7 3.633 17.7c-1.087-.744.084-.729.084-.729 1.205.084 1.838 1.236 1.838 1.236 1.07 1.835 2.809 1.305 3.495.998.108-.776.417-1.305.76-1.605-2.665-.3-5.466-1.332-5.466-5.93 0-1.31.465-2.38 1.235-3.22-.135-.303-.54-1.523.105-3.176 0 0 1.005-.322 3.3 1.23.96-.267 1.98-.399 3-.405 1.02.006 2.04.138 3 .405 2.28-1.552 3.285-1.23 3.285-1.23.645 1.653.24 2.873.12 3.176.765.84 1.23 1.91 1.23 3.22 0 4.61-2.805 5.625-5.475 5.92.42.36.81 1.096.81 2.22 0 1.606-.015 2.896-.015 3.286 0 .315.21.69.825.57C20.565 22.092 24 17.592 24 12.297c0-6.627-5.373-12-12-12"></path></svg><span class="visually-hidden" data-v-48c45ef6>github</span></a><!--]--></div></div></div><!--]--><!--]--></div></div></div><button type="button" class="VPNavBarHamburger hamburger" aria-label="mobile navigation" aria-expanded="false" aria-controls="VPNavScreen" data-v-8856f192 data-v-6f008456><span class="container" data-v-6f008456><span class="top" data-v-6f008456></span><span class="middle" data-v-6f008456></span><span class="bottom" data-v-6f008456></span></span></button></div></div></div><!----></header><div class="VPLocalNav" data-v-6b5fd0a9 data-v-92b0f14a><button class="menu" aria-expanded="false" aria-controls="VPSidebarNav" data-v-92b0f14a><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" viewbox="0 0 24 24" class="menu-icon" data-v-92b0f14a><path d="M17,11H3c-0.6,0-1-0.4-1-1s0.4-1,1-1h14c0.6,0,1,0.4,1,1S17.6,11,17,11z"></path><path d="M21,7H3C2.4,7,2,6.6,2,6s0.4-1,1-1h18c0.6,0,1,0.4,1,1S21.6,7,21,7z"></path><path d="M21,15H3c-0.6,0-1-0.4-1-1s0.4-1,1-1h18c0.6,0,1,0.4,1,1S21.6,15,21,15z"></path><path d="M17,19H3c-0.6,0-1-0.4-1-1s0.4-1,1-1h14c0.6,0,1,0.4,1,1S17.6,19,17,19z"></path></svg><span class="menu-text" data-v-92b0f14a>Menu</span></button><a class="top-link" href="#" data-v-92b0f14a> Return to top </a></div><aside class="VPSidebar" data-v-6b5fd0a9 data-v-55e4c7db><nav class="nav" id="VPSidebarNav" aria-labelledby="sidebar-aria-label" tabindex="-1" data-v-55e4c7db><span class="visually-hidden" id="sidebar-aria-label" data-v-55e4c7db> Sidebar Navigation </span><!--[--><div class="group" data-v-55e4c7db><section class="VPSidebarGroup collapsible" data-v-55e4c7db data-v-1f69a7ed><div class="title" role="button" data-v-1f69a7ed><h2 class="title-text" data-v-1f69a7ed>数据结构</h2><div class="action" data-v-1f69a7ed><svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" viewbox="0 0 24 24" class="icon minus" data-v-1f69a7ed><path d="M19,2H5C3.3,2,2,3.3,2,5v14c0,1.7,1.3,3,3,3h14c1.7,0,3-1.3,3-3V5C22,3.3,20.7,2,19,2zM20,19c0,0.6-0.4,1-1,1H5c-0.6,0-1-0.4-1-1V5c0-0.6,0.4-1,1-1h14c0.6,0,1,0.4,1,1V19z"></path><path d="M16,11H8c-0.6,0-1,0.4-1,1s0.4,1,1,1h8c0.6,0,1-0.4,1-1S16.6,11,16,11z"></path></svg><svg version="1.1" xmlns="http://www.w3.org/2000/svg" viewbox="0 0 24 24" class="icon plus" data-v-1f69a7ed><path d="M19,2H5C3.3,2,2,3.3,2,5v14c0,1.7,1.3,3,3,3h14c1.7,0,3-1.3,3-3V5C22,3.3,20.7,2,19,2z M20,19c0,0.6-0.4,1-1,1H5c-0.6,0-1-0.4-1-1V5c0-0.6,0.4-1,1-1h14c0.6,0,1,0.4,1,1V19z"></path><path d="M16,11h-3V8c0-0.6-0.4-1-1-1s-1,0.4-1,1v3H8c-0.6,0-1,0.4-1,1s0.4,1,1,1h3v3c0,0.6,0.4,1,1,1s1-0.4,1-1v-3h3c0.6,0,1-0.4,1-1S16.6,11,16,11z"></path></svg></div></div><div class="items" data-v-1f69a7ed><!--[--><a class="VPLink link" href="/vitepress-doc/kaoyan/a.html" data-v-1f69a7ed data-v-f53f775e data-v-5704c677><!--[--><span class="link-text" data-v-f53f775e>a</span><!--]--><!----></a><a class="VPLink link" href="/vitepress-doc/kaoyan/b.html" data-v-1f69a7ed data-v-f53f775e data-v-5704c677><!--[--><span class="link-text" data-v-f53f775e>b</span><!--]--><!----></a><!--]--></div></section></div><div class="group" data-v-55e4c7db><section class="VPSidebarGroup collapsible" data-v-55e4c7db data-v-1f69a7ed><div class="title" role="button" data-v-1f69a7ed><h2 class="title-text" data-v-1f69a7ed>操作系统</h2><div class="action" data-v-1f69a7ed><svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" viewbox="0 0 24 24" class="icon minus" data-v-1f69a7ed><path d="M19,2H5C3.3,2,2,3.3,2,5v14c0,1.7,1.3,3,3,3h14c1.7,0,3-1.3,3-3V5C22,3.3,20.7,2,19,2zM20,19c0,0.6-0.4,1-1,1H5c-0.6,0-1-0.4-1-1V5c0-0.6,0.4-1,1-1h14c0.6,0,1,0.4,1,1V19z"></path><path d="M16,11H8c-0.6,0-1,0.4-1,1s0.4,1,1,1h8c0.6,0,1-0.4,1-1S16.6,11,16,11z"></path></svg><svg version="1.1" xmlns="http://www.w3.org/2000/svg" viewbox="0 0 24 24" class="icon plus" data-v-1f69a7ed><path d="M19,2H5C3.3,2,2,3.3,2,5v14c0,1.7,1.3,3,3,3h14c1.7,0,3-1.3,3-3V5C22,3.3,20.7,2,19,2z M20,19c0,0.6-0.4,1-1,1H5c-0.6,0-1-0.4-1-1V5c0-0.6,0.4-1,1-1h14c0.6,0,1,0.4,1,1V19z"></path><path d="M16,11h-3V8c0-0.6-0.4-1-1-1s-1,0.4-1,1v3H8c-0.6,0-1,0.4-1,1s0.4,1,1,1h3v3c0,0.6,0.4,1,1,1s1-0.4,1-1v-3h3c0.6,0,1-0.4,1-1S16.6,11,16,11z"></path></svg></div></div><div class="items" data-v-1f69a7ed><!--[--><a class="VPLink link" href="/vitepress-doc/kaoyan/c.html" data-v-1f69a7ed data-v-f53f775e data-v-5704c677><!--[--><span class="link-text" data-v-f53f775e>c</span><!--]--><!----></a><a class="VPLink link" href="/vitepress-doc/kaoyan/d.html" data-v-1f69a7ed data-v-f53f775e data-v-5704c677><!--[--><span class="link-text" data-v-f53f775e>d</span><!--]--><!----></a><!--]--></div></section></div><!--]--></nav></aside><div class="VPContent has-sidebar" id="VPContent" data-v-6b5fd0a9 data-v-a4c57a06><div class="VPDoc has-sidebar" data-v-a4c57a06 data-v-79ca2460><div class="container" data-v-79ca2460><div class="aside" data-v-79ca2460><div class="aside-curtain" data-v-79ca2460></div><div class="aside-container" data-v-79ca2460><div class="aside-content" data-v-79ca2460><div class="VPDocAside" data-v-79ca2460 data-v-779d834d><!--[--><!--]--><!--[--><!--]--><div class="VPDocAsideOutline has-outline" data-v-779d834d data-v-51e5a8ce><div class="content" data-v-51e5a8ce><div class="outline-marker" data-v-51e5a8ce></div><div class="outline-title" data-v-51e5a8ce>On this page</div><nav aria-labelledby="doc-outline-aria-label" data-v-51e5a8ce><span class="visually-hidden" id="doc-outline-aria-label" data-v-51e5a8ce> Table of Contents for current page </span><ul class="root" data-v-51e5a8ce><!--[--><li style="" data-v-51e5a8ce><a class="outline-link" href="#_1、排序的基本概念" data-v-51e5a8ce>1、排序的基本概念</a><!----></li><li style="" data-v-51e5a8ce><a class="outline-link" href="#_2、插入类排序" data-v-51e5a8ce>2、插入类排序</a><!----></li><li style="" data-v-51e5a8ce><a class="outline-link" href="#_3、交换类排序" data-v-51e5a8ce>3、交换类排序</a><!----></li><li style="" data-v-51e5a8ce><a class="outline-link" href="#_4、选择类排序" data-v-51e5a8ce>4、选择类排序</a><!----></li><li style="" data-v-51e5a8ce><a class="outline-link" href="#_5、归并排序" data-v-51e5a8ce>5、归并排序</a><!----></li><li style="" data-v-51e5a8ce><a class="outline-link" href="#_6、基数排序" data-v-51e5a8ce>6、基数排序</a><!----></li><li style="" data-v-51e5a8ce><a class="outline-link" href="#_7、总结" data-v-51e5a8ce>7、总结</a><!----></li><!--]--></ul></nav></div></div><!--[--><!--]--><div class="spacer" data-v-779d834d></div><!--[--><!--]--><!----><!--[--><!--]--><!--[--><!--]--></div></div></div></div><div class="content" data-v-79ca2460><div class="content-container" data-v-79ca2460><!--[--><!--]--><main class="main" data-v-79ca2460><div style="position:relative;" class="vp-doc _vitepress-doc_kaoyan_ds_sort" data-v-79ca2460><div><h2 id="_1、排序的基本概念" tabindex="-1">1、排序的基本概念 <a class="header-anchor" href="#_1、排序的基本概念" aria-hidden="true">#</a></h2><ul><li>排序：重新排列表中的元素，使表中元素满足按关键字有序的过程（关键字可以相同）</li><li>排序算法的评价指标：时间复杂度、空间复杂度；</li><li><strong>排序算法的稳定性</strong>：关键字相同的元素在排序之后相对位置不变，称为稳定的； Q： 稳定的排序算法一定比不稳定的好？ A： 不一定，要看实际需求；</li><li>排序算法的分类： <ul><li>内部排序： 数据都在内存——关注如何使时间、空间复杂度更低；</li><li>外部排序： 数据太多，无法全部放入内存——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少；</li></ul></li></ul><p>口诀：</p><p>插冒归，它很稳。插冒归喜欢选冒插，插完他就方了。(插入排序、冒泡排序、归并排序是稳定排序算法。选择排序、冒泡排序插入排序的平均时间复杂度是n的二次方)</p><p>快归堆，n老二（快速排序、归并排序，堆排序平均时间复杂度为nlog2）</p><h2 id="_2、插入类排序" tabindex="-1">2、插入类排序 <a class="header-anchor" href="#_2、插入类排序" aria-hidden="true">#</a></h2><h3 id="_2-1-直接插入" tabindex="-1">2.1 直接插入 <a class="header-anchor" href="#_2-1-直接插入" aria-hidden="true">#</a></h3><p><strong>算法过程描述</strong>：</p><p>把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。</p><p><img src="https://lionkliu-typore.oss-cn-shanghai.aliyuncs.com/blog-img/202209101130613.jpeg" alt="img"></p><p><strong>代码实现</strong>：</p><div class="language-c"><span class="copy"></span><pre><code><span class="line"><span style="color:#676E95;font-style:italic;">/**</span></span>
<span class="line"><span style="color:#676E95;font-style:italic;"> * 插入排序</span></span>
<span class="line"><span style="color:#676E95;font-style:italic;"> * </span><span style="color:#C792EA;font-style:italic;">@param</span><span style="color:#676E95;font-style:italic;"> </span><span style="color:#A6ACCD;font-style:italic;">arr</span><span style="color:#676E95;font-style:italic;"> 待排序列</span></span>
<span class="line"><span style="color:#676E95;font-style:italic;"> * </span><span style="color:#C792EA;font-style:italic;">@param</span><span style="color:#676E95;font-style:italic;"> </span><span style="color:#A6ACCD;font-style:italic;">n</span><span style="color:#676E95;font-style:italic;"> 待排序列元素个数</span></span>
<span class="line"><span style="color:#676E95;font-style:italic;"> */</span></span>
<span class="line"><span style="color:#C792EA;">void</span><span style="color:#A6ACCD;"> </span><span style="color:#82AAFF;">InsertSort</span><span style="color:#89DDFF;">(</span><span style="color:#C792EA;">int</span><span style="color:#A6ACCD;"> arr</span><span style="color:#C792EA;">[]</span><span style="color:#89DDFF;">,</span><span style="color:#A6ACCD;"> </span><span style="color:#C792EA;">int</span><span style="color:#A6ACCD;"> n</span><span style="color:#89DDFF;">)</span><span style="color:#A6ACCD;"> </span><span style="color:#89DDFF;">{</span></span>
<span class="line"><span style="color:#F07178;">    </span><span style="color:#C792EA;">int</span><span style="color:#F07178;"> i</span><span style="color:#89DDFF;">,</span><span style="color:#F07178;"> j</span><span style="color:#89DDFF;">,</span><span style="color:#F07178;"> tmp</span><span style="color:#89DDFF;">;</span></span>
<span class="line"><span style="color:#F07178;">    </span><span style="color:#89DDFF;font-style:italic;">for</span><span style="color:#F07178;"> </span><span style="color:#89DDFF;">(</span><span style="color:#F07178;">i </span><span style="color:#89DDFF;">=</span><span style="color:#F07178;"> </span><span style="color:#F78C6C;">1</span><span style="color:#89DDFF;">;</span><span style="color:#F07178;"> i </span><span style="color:#89DDFF;">&lt;</span><span style="color:#F07178;"> n </span><span style="color:#89DDFF;">;</span><span style="color:#F07178;"> i</span><span style="color:#89DDFF;">++)</span><span style="color:#F07178;"> </span><span style="color:#89DDFF;">{</span></span>
<span class="line"><span style="color:#89DDFF;">        </span><span style="color:#676E95;font-style:italic;">// 关键字小于前驱</span></span>
<span class="line"><span style="color:#F07178;">        </span><span style="color:#89DDFF;font-style:italic;">if</span><span style="color:#F07178;"> </span><span style="color:#89DDFF;">(</span><span style="color:#A6ACCD;">arr</span><span style="color:#89DDFF;">[</span><span style="color:#F07178;">i</span><span style="color:#89DDFF;">]</span><span style="color:#F07178;"> </span><span style="color:#89DDFF;">&lt;</span><span style="color:#F07178;"> </span><span style="color:#A6ACCD;">arr</span><span style="color:#89DDFF;">[</span><span style="color:#F07178;">i </span><span style="color:#89DDFF;">-</span><span style="color:#F07178;"> </span><span style="color:#F78C6C;">1</span><span style="color:#89DDFF;">])</span><span style="color:#F07178;"> </span><span style="color:#89DDFF;">{</span></span>
<span class="line"><span style="color:#89DDFF;">            </span><span style="color:#676E95;font-style:italic;">// 从无序列表中取出第一个元素</span></span>
<span class="line"><span style="color:#F07178;">            tmp </span><span style="color:#89DDFF;">=</span><span style="color:#F07178;"> </span><span style="color:#A6ACCD;">arr</span><span style="color:#89DDFF;">[</span><span style="color:#F07178;">i</span><span style="color:#89DDFF;">];</span></span>
<span class="line"><span style="color:#F07178;">            </span><span style="color:#89DDFF;font-style:italic;">for</span><span style="color:#F07178;"> </span><span style="color:#89DDFF;">(</span><span style="color:#F07178;"> j </span><span style="color:#89DDFF;">=</span><span style="color:#F07178;"> i </span><span style="color:#89DDFF;">-</span><span style="color:#F07178;"> </span><span style="color:#F78C6C;">1</span><span style="color:#89DDFF;">;</span><span style="color:#F07178;"> j </span><span style="color:#89DDFF;">&gt;=</span><span style="color:#F07178;"> </span><span style="color:#F78C6C;">0</span><span style="color:#F07178;"> </span><span style="color:#89DDFF;">&amp;&amp;</span><span style="color:#F07178;"> </span><span style="color:#A6ACCD;">arr</span><span style="color:#89DDFF;">[</span><span style="color:#F07178;">j</span><span style="color:#89DDFF;">]</span><span style="color:#F07178;"> </span><span style="color:#89DDFF;">&gt;</span><span style="color:#F07178;"> tmp</span><span style="color:#89DDFF;">;</span><span style="color:#F07178;"> </span><span style="color:#89DDFF;">--</span><span style="color:#F07178;">j</span><span style="color:#89DDFF;">)</span><span style="color:#F07178;"> </span><span style="color:#89DDFF;">{</span></span>
<span class="line"><span style="color:#89DDFF;">                </span><span style="color:#676E95;font-style:italic;">// 所有大于temp的元素都向后挪</span></span>
<span class="line"><span style="color:#F07178;">                </span><span style="color:#A6ACCD;">arr</span><span style="color:#89DDFF;">[</span><span style="color:#F07178;">j </span><span style="color:#89DDFF;">+</span><span style="color:#F07178;"> </span><span style="color:#F78C6C;">1</span><span style="color:#89DDFF;">]</span><span style="color:#F07178;"> </span><span style="color:#89DDFF;">=</span><span style="color:#F07178;"> </span><span style="color:#A6ACCD;">arr</span><span style="color:#89DDFF;">[</span><span style="color:#F07178;">j</span><span style="color:#89DDFF;">];</span></span>
<span class="line"><span style="color:#F07178;">            </span><span style="color:#89DDFF;">}</span></span>
<span class="line"><span style="color:#89DDFF;">            </span><span style="color:#676E95;font-style:italic;">// 一趟排序完成说明已将无序表中的第一个元素移到了有序表中合适位置了</span></span>
<span class="line"><span style="color:#F07178;">            </span><span style="color:#A6ACCD;">arr</span><span style="color:#89DDFF;">[</span><span style="color:#F07178;">j </span><span style="color:#89DDFF;">+</span><span style="color:#F07178;"> </span><span style="color:#F78C6C;">1</span><span style="color:#89DDFF;">]</span><span style="color:#F07178;"> </span><span style="color:#89DDFF;">=</span><span style="color:#F07178;"> tmp</span><span style="color:#89DDFF;">;</span></span>
<span class="line"><span style="color:#F07178;">        </span><span style="color:#89DDFF;">}</span></span>
<span class="line"><span style="color:#F07178;">    </span><span style="color:#89DDFF;">}</span></span>
<span class="line"><span style="color:#89DDFF;">}</span></span>
<span class="line"></span></code></pre></div><p><strong>算法效率分析</strong>：</p><ul><li>空间复杂度：<code>O(1)</code></li><li>时间复杂度：主要来自于对比关键字、移动关键字，若有n个元素，则需要n-1躺处理 <ul><li><strong>最好情况：</strong> 原本为有序，共n-1趟处理，每一趟都只需要对比1次关键字，不需要移动元素，共对比n-1次 —— <code>O(n)</code></li><li><strong>最差情况：</strong> 原本为逆序 —— <code>O(n²)</code></li><li><strong>平均情况：</strong> <code>O(n²)</code></li></ul></li><li>算法稳定性：稳定</li></ul><h3 id="_2-2-折半插入" tabindex="-1">2.2 折半插入 <a class="header-anchor" href="#_2-2-折半插入" aria-hidden="true">#</a></h3><p><strong>算法过程描述</strong></p><ul><li><p>先用折半查找找到应该插入的位置，再移动元素；</p></li><li><p>为了保证稳定性，当查找到和插入元素关键字一样的元素时，应该继续在这个元素的右半部分继续查找以确认位置; 即当<code> A[mid] == A[0]</code> 时，应继续在mid所指位置右边寻找插入位置</p></li><li><p>当 <code>low &gt; high</code> 时，折半查找停止，应将 <code>[low,i-1]or[high+1,i-1]</code>内的元素全部右移，并将A[0]复制到low所指的位置；</p></li></ul><p><strong>代码实现</strong></p><div class="language-c"><span class="copy"></span><pre><code><span class="line"></span>
<span class="line"></span></code></pre></div><p><strong>算法效率分析</strong></p><ul><li>与<code>直接插入排序</code>相比，比较关键字的次数减少了，但是移动元素的次数没有变，<strong>时间复杂度仍然是O(n²)</strong></li></ul><h3 id="_2-3-希尔排序" tabindex="-1">2.3 希尔排序 <a class="header-anchor" href="#_2-3-希尔排序" aria-hidden="true">#</a></h3><p><strong>算法过程描述</strong></p><p><strong>代码实现</strong></p><div class="language-c"><span class="copy"></span><pre><code><span class="line"></span>
<span class="line"></span></code></pre></div><p><strong>算法效率分析</strong></p><ul><li>空间复杂度：</li><li>时间复杂度：</li></ul><h2 id="_3、交换类排序" tabindex="-1">3、交换类排序 <a class="header-anchor" href="#_3、交换类排序" aria-hidden="true">#</a></h2><p><strong>基本思想</strong>：基于交换的排序，根据序列中两个元素关键字比较结果来交换位置</p><h3 id="_3-1-冒泡排序" tabindex="-1">3.1 冒泡排序 <a class="header-anchor" href="#_3-1-冒泡排序" aria-hidden="true">#</a></h3><p><strong>算法过程描述</strong></p><ul><li>每一趟冒泡的结果都是把序列中最小元素放到序列的最终位置。这样只需<code>n - 1</code> 趟冒泡就能把所有元素排好序。</li><li>为保证稳定性，关键字相同的元素不交换；</li></ul><img src="https://lionkliu-typore.oss-cn-shanghai.aliyuncs.com/blog-img/202209091712273.jpeg" alt="img" style="zoom:80%;"><p><strong>代码实现</strong></p><div class="language-c"><span class="copy"></span><pre><code><span class="line"><span style="color:#676E95;font-style:italic;">/**</span></span>
<span class="line"><span style="color:#676E95;font-style:italic;"> * 交换两个元素</span></span>
<span class="line"><span style="color:#676E95;font-style:italic;"> * </span><span style="color:#C792EA;font-style:italic;">@param</span><span style="color:#676E95;font-style:italic;"> </span><span style="color:#A6ACCD;font-style:italic;">a</span></span>
<span class="line"><span style="color:#676E95;font-style:italic;"> * </span><span style="color:#C792EA;font-style:italic;">@param</span><span style="color:#676E95;font-style:italic;"> </span><span style="color:#A6ACCD;font-style:italic;">b</span></span>
<span class="line"><span style="color:#676E95;font-style:italic;"> */</span></span>
<span class="line"><span style="color:#C792EA;">void</span><span style="color:#A6ACCD;"> </span><span style="color:#82AAFF;">swap</span><span style="color:#89DDFF;">(</span><span style="color:#C792EA;">int</span><span style="color:#A6ACCD;"> </span><span style="color:#89DDFF;">&amp;</span><span style="color:#A6ACCD;">a</span><span style="color:#89DDFF;">,</span><span style="color:#A6ACCD;"> </span><span style="color:#C792EA;">int</span><span style="color:#A6ACCD;"> </span><span style="color:#89DDFF;">&amp;</span><span style="color:#A6ACCD;">b</span><span style="color:#89DDFF;">)</span><span style="color:#A6ACCD;"> </span><span style="color:#89DDFF;">{</span></span>
<span class="line"><span style="color:#F07178;">    </span><span style="color:#C792EA;">int</span><span style="color:#F07178;"> tmp </span><span style="color:#89DDFF;">=</span><span style="color:#F07178;"> a</span><span style="color:#89DDFF;">;</span></span>
<span class="line"><span style="color:#F07178;">    a </span><span style="color:#89DDFF;">=</span><span style="color:#F07178;"> b</span><span style="color:#89DDFF;">;</span></span>
<span class="line"><span style="color:#F07178;">    b </span><span style="color:#89DDFF;">=</span><span style="color:#F07178;"> tmp</span><span style="color:#89DDFF;">;</span></span>
<span class="line"><span style="color:#89DDFF;">}</span></span>
<span class="line"></span>
<span class="line"><span style="color:#676E95;font-style:italic;">/**</span></span>
<span class="line"><span style="color:#676E95;font-style:italic;"> * 冒泡排序</span></span>
<span class="line"><span style="color:#676E95;font-style:italic;"> * </span><span style="color:#C792EA;font-style:italic;">@param</span><span style="color:#676E95;font-style:italic;"> </span><span style="color:#A6ACCD;font-style:italic;">arr</span><span style="color:#676E95;font-style:italic;"> : 待排序列</span></span>
<span class="line"><span style="color:#676E95;font-style:italic;"> * </span><span style="color:#C792EA;font-style:italic;">@param</span><span style="color:#676E95;font-style:italic;"> </span><span style="color:#A6ACCD;font-style:italic;">n</span><span style="color:#676E95;font-style:italic;"> ：序列个数</span></span>
<span class="line"><span style="color:#676E95;font-style:italic;"> */</span></span>
<span class="line"><span style="color:#C792EA;">void</span><span style="color:#A6ACCD;"> </span><span style="color:#82AAFF;">BubbleSort</span><span style="color:#89DDFF;">(</span><span style="color:#C792EA;">int</span><span style="color:#A6ACCD;"> arr</span><span style="color:#C792EA;">[]</span><span style="color:#89DDFF;">,</span><span style="color:#A6ACCD;"> </span><span style="color:#C792EA;">int</span><span style="color:#A6ACCD;"> n</span><span style="color:#89DDFF;">)</span><span style="color:#A6ACCD;"> </span><span style="color:#89DDFF;">{</span></span>
<span class="line"><span style="color:#89DDFF;">    </span><span style="color:#676E95;font-style:italic;">// n - 1 趟排序</span></span>
<span class="line"><span style="color:#F07178;">    </span><span style="color:#89DDFF;font-style:italic;">for</span><span style="color:#F07178;"> </span><span style="color:#89DDFF;">(</span><span style="color:#C792EA;">int</span><span style="color:#F07178;"> i </span><span style="color:#89DDFF;">=</span><span style="color:#F07178;"> </span><span style="color:#F78C6C;">0</span><span style="color:#89DDFF;">;</span><span style="color:#F07178;"> i </span><span style="color:#89DDFF;">&lt;</span><span style="color:#F07178;"> n </span><span style="color:#89DDFF;">-</span><span style="color:#F07178;"> </span><span style="color:#F78C6C;">1</span><span style="color:#89DDFF;">;</span><span style="color:#F07178;"> </span><span style="color:#89DDFF;">++</span><span style="color:#F07178;">i</span><span style="color:#89DDFF;">)</span><span style="color:#F07178;"> </span><span style="color:#89DDFF;">{</span></span>
<span class="line"><span style="color:#89DDFF;">        </span><span style="color:#676E95;font-style:italic;">// 标识本趟冒泡是否交换</span></span>
<span class="line"><span style="color:#F07178;">        </span><span style="color:#C792EA;">bool</span><span style="color:#F07178;"> flag </span><span style="color:#89DDFF;">=</span><span style="color:#F07178;"> </span><span style="color:#89DDFF;">false;</span></span>
<span class="line"><span style="color:#89DDFF;">        </span><span style="color:#676E95;font-style:italic;">// 每一趟冒泡比较的过程</span></span>
<span class="line"><span style="color:#F07178;">        </span><span style="color:#89DDFF;font-style:italic;">for</span><span style="color:#F07178;"> </span><span style="color:#89DDFF;">(</span><span style="color:#C792EA;">int</span><span style="color:#F07178;"> j </span><span style="color:#89DDFF;">=</span><span style="color:#F07178;"> n </span><span style="color:#89DDFF;">-</span><span style="color:#F07178;"> </span><span style="color:#F78C6C;">1</span><span style="color:#89DDFF;">;</span><span style="color:#F07178;"> j </span><span style="color:#89DDFF;">&gt;</span><span style="color:#F07178;"> i</span><span style="color:#89DDFF;">;</span><span style="color:#F07178;"> j</span><span style="color:#89DDFF;">--)</span><span style="color:#F07178;"> </span><span style="color:#89DDFF;">{</span></span>
<span class="line"><span style="color:#F07178;">            </span><span style="color:#89DDFF;font-style:italic;">if</span><span style="color:#F07178;"> </span><span style="color:#89DDFF;">(</span><span style="color:#A6ACCD;">arr</span><span style="color:#89DDFF;">[</span><span style="color:#F07178;">j </span><span style="color:#89DDFF;">-</span><span style="color:#F07178;"> </span><span style="color:#F78C6C;">1</span><span style="color:#89DDFF;">]</span><span style="color:#F07178;"> </span><span style="color:#89DDFF;">&gt;</span><span style="color:#F07178;"> </span><span style="color:#A6ACCD;">arr</span><span style="color:#89DDFF;">[</span><span style="color:#F07178;">j</span><span style="color:#89DDFF;">])</span><span style="color:#F07178;"> </span><span style="color:#89DDFF;">{</span></span>
<span class="line"><span style="color:#F07178;">                </span><span style="color:#82AAFF;">swap</span><span style="color:#89DDFF;">(</span><span style="color:#A6ACCD;">arr</span><span style="color:#89DDFF;">[</span><span style="color:#F07178;">j </span><span style="color:#89DDFF;">-</span><span style="color:#F07178;"> </span><span style="color:#F78C6C;">1</span><span style="color:#89DDFF;">],</span><span style="color:#F07178;"> </span><span style="color:#A6ACCD;">arr</span><span style="color:#89DDFF;">[</span><span style="color:#F07178;">j</span><span style="color:#89DDFF;">]);</span></span>
<span class="line"><span style="color:#F07178;">                flag </span><span style="color:#89DDFF;">=</span><span style="color:#F07178;"> </span><span style="color:#89DDFF;">true;</span></span>
<span class="line"><span style="color:#F07178;">            </span><span style="color:#89DDFF;">}</span></span>
<span class="line"><span style="color:#F07178;">        </span><span style="color:#89DDFF;">}</span></span>
<span class="line"><span style="color:#89DDFF;">        </span><span style="color:#676E95;font-style:italic;">// 如果本趟遍历后没有发生交换，说明表已经有序，可以结束算法</span></span>
<span class="line"><span style="color:#F07178;">        </span><span style="color:#89DDFF;font-style:italic;">if</span><span style="color:#F07178;"> </span><span style="color:#89DDFF;">(</span><span style="color:#F07178;">flag</span><span style="color:#89DDFF;">)</span><span style="color:#F07178;"> </span><span style="color:#89DDFF;">{</span></span>
<span class="line"><span style="color:#F07178;">            </span><span style="color:#89DDFF;font-style:italic;">return</span><span style="color:#89DDFF;">;</span></span>
<span class="line"><span style="color:#F07178;">        </span><span style="color:#89DDFF;">}</span></span>
<span class="line"><span style="color:#F07178;">    </span><span style="color:#89DDFF;">}</span></span>
<span class="line"><span style="color:#89DDFF;">}</span></span>
<span class="line"></span></code></pre></div><p><strong>算法效率分析</strong></p><ul><li>空间复杂度：O(1)</li><li>时间复杂度： <ul><li>最好情况 (有序) ：只需要一趟排序，比较次数=n-1，交换次数=0，最好时间复杂度=<code>O(n)</code></li><li>最坏情况 (逆序) ：比较次数 = (n-1)+(n-2)+...+1 = n(n-1)/2 = 交换次数，最坏时间复杂度 = <code>O(n²)</code></li><li>平均时间复杂度 = O(n²)</li></ul></li><li>稳定性：稳定</li></ul><h3 id="_3-2-快速排序" tabindex="-1">3.2 快速排序 <a class="header-anchor" href="#_3-2-快速排序" aria-hidden="true">#</a></h3><p><strong>算法过程描述</strong></p><p>选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分；其中一部分的所有数据都比另外一部分的所有数据都要小。然后，再按此方法对这两部分数据分别进行快速排序，整个排序过程可以<strong>递归进行</strong>，以此达到整个数据变成有序序列。</p><ul><li>每一趟排序都可使一个<strong>中间元素确定其最终位置</strong></li><li>用一个元素（不一定是第一个）把待排序序列“划分”为两个部分，左边更小，右边更大，该元素的最终位置已确认</li></ul><p><img src="https://lionkliu-typore.oss-cn-shanghai.aliyuncs.com/blog-img/202209101106783.jpeg" alt="img"></p><p><strong>代码实现</strong></p><div class="language-c"><span class="copy"></span><pre><code><span class="line"></span>
<span class="line"></span></code></pre></div><p><strong>算法效率分析</strong></p><ul><li><p>每一层的<code>QuickSort</code>只需要处理剩余的待排序元素，时间复杂度不超过O(n);</p></li><li><p>把n个元素组织成二叉树，二叉树的层数就是递归调用的层数，n个结点的二叉树<strong>最小高度</strong> = <code>⌊log₂n⌋ + 1</code>, <strong>最大高度</strong> = <code>n</code></p></li><li><p><strong>空间复杂度</strong> ：<strong>O(递归层数)</strong>（递归层数最小为log₂n）</p><ul><li>最好 = <code>O(log₂n)</code></li><li>最坏 = <code>O(n)</code></li></ul></li><li><p><strong>时间复杂度</strong>：<strong>O(n×递归层数)</strong> （递归层数最大为n）</p><ul><li>最好 = <code>O(nlog₂n)</code> : 若每一次选中的“枢轴”可以将待排序序列划分为<strong>均匀</strong>的两个部分，则递归深度最小，算法效率最高；</li><li>最坏 = <code>O(n²)</code> ：序列本就有序或逆序，此时时间、空间复杂度最高；</li></ul></li><li><p><strong>稳定性</strong>：不稳定</p></li><li><p>快速排序使所有内部排序算法中平均<strong>性能最优</strong>的排序算法；</p></li><li><p><strong>快速排序算法优化思路：</strong> 尽量选择可以把数据中分的枢轴元素</p><ul><li>选头、中、尾三个位置的元素，取中间值作为枢轴元素；</li><li>随机选一个元素作为枢轴元素；</li></ul></li></ul><h2 id="_4、选择类排序" tabindex="-1">4、选择类排序 <a class="header-anchor" href="#_4、选择类排序" aria-hidden="true">#</a></h2><h3 id="_4-1-简单选择排序" tabindex="-1">4.1 简单选择排序 <a class="header-anchor" href="#_4-1-简单选择排序" aria-hidden="true">#</a></h3><p><strong>算法过程描述</strong></p><p>每一趟在待排元素中找到最小元素加入有序子序列的末尾，n 个元素只需 n - 1趟处理</p><p><img src="https://lionkliu-typore.oss-cn-shanghai.aliyuncs.com/blog-img/202209112045871.jpeg" alt="img"></p><p><strong>代码实现</strong></p><div class="language-c"><span class="copy"></span><pre><code><span class="line"></span>
<span class="line"></span></code></pre></div><p><strong>算法效率分析</strong></p><ul><li>空间复杂度：</li><li>时间复杂度：</li></ul><h3 id="_4-2-堆排序" tabindex="-1">4.2 堆排序 <a class="header-anchor" href="#_4-2-堆排序" aria-hidden="true">#</a></h3><p><strong>算法过程描述</strong></p><p><strong>代码实现</strong></p><div class="language-c"><span class="copy"></span><pre><code><span class="line"></span>
<span class="line"></span></code></pre></div><p><strong>算法效率分析</strong></p><ul><li>空间复杂度：</li><li>时间复杂度：</li></ul><h2 id="_5、归并排序" tabindex="-1">5、归并排序 <a class="header-anchor" href="#_5、归并排序" aria-hidden="true">#</a></h2><p><strong>算法过程描述</strong></p><p><strong>代码实现</strong></p><div class="language-c"><span class="copy"></span><pre><code><span class="line"></span>
<span class="line"></span></code></pre></div><p><strong>算法效率分析</strong></p><ul><li>空间复杂度：</li><li>时间复杂度：</li></ul><h2 id="_6、基数排序" tabindex="-1">6、基数排序 <a class="header-anchor" href="#_6、基数排序" aria-hidden="true">#</a></h2><p><strong>算法过程描述</strong></p><p><strong>代码实现</strong></p><div class="language-c"><span class="copy"></span><pre><code><span class="line"></span>
<span class="line"></span></code></pre></div><p><strong>算法效率分析</strong></p><ul><li></li><li></li></ul><h2 id="_7、总结" tabindex="-1">7、总结 <a class="header-anchor" href="#_7、总结" aria-hidden="true">#</a></h2><p><img src="https://lionkliu-typore.oss-cn-shanghai.aliyuncs.com/blog-img/202209101059332.png" alt="image-20220910105932104"></p><ol><li>稳定的排序算法：</li><li>不稳定的排序算法：</li></ol><hr><p>参考：</p><p><a href="https://www.pdai.tech/md/algorithm" target="_blank" rel="noopener noreferrer">https://www.pdai.tech/md/algorithm</a></p><p><a href="https://blog.csdn.net/weixin_45016439/article/details/115742183" target="_blank" rel="noopener noreferrer">https://blog.csdn.net/weixin_45016439/article/details/115742183</a></p></div></div></main><footer class="VPDocFooter" data-v-79ca2460 data-v-04568844><div class="edit-info" data-v-04568844><div class="edit-link" data-v-04568844><a class="VPLink link edit-link-button" href="https://github.com/vuejs/vitepress/edit/main/docs/kaoyan/ds/sort.md" target="_blank" rel="noopener noreferrer" data-v-04568844 data-v-5704c677><!--[--><svg xmlns="http://www.w3.org/2000/svg" viewbox="0 0 24 24" class="edit-link-icon" data-v-04568844><path d="M18,23H4c-1.7,0-3-1.3-3-3V6c0-1.7,1.3-3,3-3h7c0.6,0,1,0.4,1,1s-0.4,1-1,1H4C3.4,5,3,5.4,3,6v14c0,0.6,0.4,1,1,1h14c0.6,0,1-0.4,1-1v-7c0-0.6,0.4-1,1-1s1,0.4,1,1v7C21,21.7,19.7,23,18,23z"></path><path d="M8,17c-0.3,0-0.5-0.1-0.7-0.3C7,16.5,6.9,16.1,7,15.8l1-4c0-0.2,0.1-0.3,0.3-0.5l9.5-9.5c1.2-1.2,3.2-1.2,4.4,0c1.2,1.2,1.2,3.2,0,4.4l-9.5,9.5c-0.1,0.1-0.3,0.2-0.5,0.3l-4,1C8.2,17,8.1,17,8,17zM9.9,12.5l-0.5,2.1l2.1-0.5l9.3-9.3c0.4-0.4,0.4-1.1,0-1.6c-0.4-0.4-1.2-0.4-1.6,0l0,0L9.9,12.5z M18.5,2.5L18.5,2.5L18.5,2.5z"></path></svg> Edit this page on GitHub<!--]--><!----></a></div><!----></div><div class="prev-next" data-v-04568844><div class="pager" data-v-04568844><!----></div><div class="pager" data-v-04568844><a class="pager-link next" href="/vitepress-doc/kaoyan/a.html" data-v-04568844><span class="desc" data-v-04568844>Next page</span><span class="title" data-v-04568844>a</span></a></div></div></footer><!--[--><!--]--></div></div></div></div></div><footer class="VPFooter has-sidebar" data-v-6b5fd0a9 data-v-5b331722><div class="container" data-v-5b331722><p class="message" data-v-5b331722>Released under the MIT License.</p><p class="copyright" data-v-5b331722>Copyright © 2022-present lionkliu</p></div></footer><!--[--><!--]--></div></div>
    <script>__VP_HASH_MAP__ = JSON.parse("{\"index.md\":\"d20559cb\",\"kaoyan_a.md\":\"1aedffd1\",\"kaoyan_b.md\":\"71529d71\",\"kaoyan_c.md\":\"2748357a\",\"kaoyan_d.md\":\"b409564a\",\"kaoyan_ds_sort.md\":\"73d4d399\",\"kaoyan_index.md\":\"7d8c4113\",\"kaoyan_os_thread-1.md\":\"00939a78\",\"menu1_a.md\":\"c28519ee\",\"menu1_b.md\":\"ce86af96\",\"menu1_c.md\":\"935dbc90\",\"menu1_d.md\":\"50a45bf1\",\"menu1_index.md\":\"219887a4\",\"menu3_a.md\":\"11d40c6e\",\"menu3_b.md\":\"8b78a530\",\"menu3_c.md\":\"9f860e70\",\"menu3_d.md\":\"9af4c9ec\",\"menu3_index.md\":\"f9a51801\",\"wiki_a.md\":\"c864682a\",\"wiki_b.md\":\"0de0976f\",\"wiki_c.md\":\"a3feb172\",\"wiki_d.md\":\"69df82f6\",\"wiki_index.md\":\"ded3d764\",\"wiki_javascript-arr.md\":\"792f707d\",\"wiki_ts-base.md\":\"e569397f\"}")</script>
    <script type="module" async src="/vitepress-doc/assets/app.397cc5b7.js"></script>
    
  </body>
</html>